package com.zp.self.module.level_4_算法练习.数据结构.栈与队列;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author By ZengPeng
 */
public class 力扣_150_逆波兰表达式求值 {
    @Test
    public void main() {

        System.out.println(evalRPN(new String[]{"2"}));
        System.out.println(evalRPN(new String[]{"2","1","+","3","*"}));
        System.out.println(evalRPN(new String[]{"4","13","5","/","+"}));
        System.out.println(evalRPN(new String[]{"10","6","9","3","+","-11","*","/","*","17","+","5","+"}));
    }

    /**
    题目：根据 逆波兰表示法，求表达式的值。
         有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
         注意 两个整数之间的除法只保留整数部分。
         可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

     示例 1：
     输入：tokens = ["2","1","+","3","*"]
     输出：9
     解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

     示例 2：
     输入：tokens = ["4","13","5","/","+"]
     输出：6
     解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

     示例 3：
     输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
     输出：22
     解释：该算式转化为常见的中缀算术表达式为：
     ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
     = ((10 * (6 / (12 * -11))) + 17) + 5
     = ((10 * (6 / -132)) + 17) + 5
     = ((10 * 0) + 17) + 5
     = (0 + 17) + 5
     = 17 + 5
     = 22

    分析：【P 💔💔】
       1.栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
                --执行用时：5 ms, 在所有 Java 提交中击败了93.57%的用户
                --时长：15分钟

    边界值 & 注意点：
       1.
     **/
    public int evalRPN(String[] tokens) {
        Deque<Integer> deque = new ArrayDeque<>();
        Integer shang,xia;
        for (String str : tokens) {
            switch (str){
                case "+":
                    deque.add(deque.pollLast()+deque.pollLast());
                    break;
                case "-":
                    shang = deque.pollLast();
                    xia = deque.pollLast();
                    deque.add(xia-shang);
                    break;
                case "*":
                    deque.add(deque.pollLast()*deque.pollLast());
                    break;
                case "/":
                    shang = deque.pollLast();
                    xia = deque.pollLast();
                    deque.add(xia/shang);
                    break;
                default:
                    deque.add(Integer.parseInt(str));
            }
        }
        return deque.pollLast();
    }
}
